import { Compare, defaultCompare } from "./util";
import { Node } from "./node";
// 二叉搜索树
export default class BinarySearchTree {
  constructor(compareFn = defaultCompare) {
    this.compareFn = compareFn;
    this.root = undefined;
  }
  // 向树中插入一个新的键
  insert(key, deeperLevel) {
    // special case: first key
    if (this.root == null) {
      this.root = new Node(key);
      this.root.level = 0; //第0层
      // echarts图表节点宽度算法
      // this.root.x = 2 ** (deeperLevel + 7);
      // 设置为当前浏览器宽度
      this.root.x = document.body.clientWidth;
      this.root.y = 0;
    } else {
      this.insertNode(this.root, key, deeperLevel);
    }
  }
  insertNode(node, key, deeperLevel) {
    if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
      if (node.left == null) {
        node.left = new Node(key);
        // 记录当前node的层数
        node.left.level = node.level + 1;
        // echarts图表节点宽度算法，子节点是父节点宽度的一半
        node.left.x = node.x - this.root.x / 2 ** node.left.level;
        // 每层深度+100
        node.left.y = node.y + 100 * deeperLevel;
        // 记录图表当前节点的指向
        node.leftTarget = node.left.toString();
      } else {
        this.insertNode(node.left, key, deeperLevel);
      }
    } else if (node.right == null) {
      node.right = new Node(key);
      node.right.level = node.level + 1;
      node.right.x = node.x + this.root.x / 2 ** node.right.level;
      node.right.y = node.y + 100 * deeperLevel;
      node.rightRarget = node.right.toString();
    } else {
      this.insertNode(node.right, key, deeperLevel);
    }
  }
  // 获取树头
  getRoot() {
    return this.root;
  }
  // 在树中查找一个键，如果节点存在，则返回true；如果不存在，则返回false
  search(key) {
    return this.searchNode(this.root, key);
  }
  searchNode(node, key) {
    if (node == null) {
      return false;
    }
    if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
      return this.searchNode(node.left, key);
    } else if (this.compareFn(key, node.key) === Compare.BIGGER_THAN) {
      return this.searchNode(node.right, key);
    }
    return true;
  }
  // 通过中序遍历方式遍历所有节点
  inOrderTraverse(callback) {
    this.inOrderTraverseNode(this.root, callback);
  }
  inOrderTraverseNode(node, callback) {
    if (node != null) {
      this.inOrderTraverseNode(node.left, callback);
      callback(node);
      this.inOrderTraverseNode(node.right, callback);
    }
  }
  // 通过先序遍历方式遍历所有节点
  preOrderTraverse(callback) {
    this.preOrderTraverseNode(this.root, callback);
  }
  preOrderTraverseNode(node, callback) {
    if (node != null) {
      callback(node);
      this.preOrderTraverseNode(node.left, callback);
      this.preOrderTraverseNode(node.right, callback);
    }
  }
  // 通过后序遍历方式遍历所有节点
  postOrderTraverse(callback) {
    this.postOrderTraverseNode(this.root, callback);
  }
  postOrderTraverseNode(node, callback) {
    if (node != null) {
      this.postOrderTraverseNode(node.left, callback);
      this.postOrderTraverseNode(node.right, callback);
      callback(node);
    }
  }
  // 返回树中最小的值/键（最左边最下面那个）
  min() {
    return this.minNode(this.root);
  }
  minNode(node) {
    let current = node;
    while (current != null && current.left != null) {
      current = current.left;
    }
    return current;
  }
  // 返回树中最大的值/键（最右边最下面那个）
  max() {
    return this.maxNode(this.root);
  }
  maxNode(node) {
    let current = node;
    while (current != null && current.right != null) {
      current = current.right;
    }
    return current;
  }
  // 从树中移除某个键
  remove(key) {
    this.root = this.removeNode(this.root, key);
  }
  removeNode(node, key) {
    if (node == null) {
      return undefined;
    }
    if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
      node.left = this.removeNode(node.left, key);
      return node;
    } else if (this.compareFn(key, node.key) === Compare.BIGGER_THAN) {
      node.right = this.removeNode(node.right, key);
      return node;
    }
    // 键和node.key相等
    // 就需要处理三种不同的情况
    // 1 - 移除一个叶节点
    // 2 - 移除有一个左侧或右侧子节点的节点
    // 3 - 移除有两个子节点的节点
    // 情况 1
    if (node.left == null && node.right == null) {
      // 这个节点没有任何子节点，但是它有一个父节点，需要通过返回null来将对应的父节点指针赋予null值
      node = null;
      return node;
    }
    // 情况 2
    if (node.left == null) {
      node = node.right;
      return node;
    } else if (node.right == null) {
      node = node.left;
      return node;
    }
    // 情况 3
    // 当找到了要移除的节点后，需要找到它右边子树中最小的节点（它的继承者）aux
    const aux = this.minNode(node.right);
    node.key = aux.key;
    // 但是，这样在树中就有两个拥有相同键的节点了，这是不行的。
    // 要继续把右侧子树中的最小节点移除，毕竟它已经被移至要移除的节点的位置了
    node.right = this.removeNode(node.right, aux.key);
    return node;
  }
}
